package com.sise.Tree;

/**
 *      剑指 Offer 33. 二叉搜索树的后序遍历序列
 *
 *      输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。
 *      参考以下这颗二叉搜索树：
 *
 *          5
 *         / \
 *        2   6
 *       / \
 *      1   3
 *
 *      输入: [1,6,3,2,5]
 *      输出: false
 *      示例 2：
 *
 *      输入: [1,3,2,6,5]
 *      输出: true
 */
public class _offer_33_verifyPostorder {

    public boolean verifyPostorder(int[] postorder) {
        return recur(postorder, 0, postorder.length - 1);
    }

    private boolean recur(int[] postorder, int left, int right) {
        if (left >= right) return true;                 // 当 i ≥ j ，说明此子树节点数量 ≤ 1，无需判别正确性，因此直接返回 true

        int fin = left;
        while (postorder[fin] < postorder[right]){      // 找到第一个比 根节点大的 节点
            fin++;                                      // 根据此时的索引分为 左右子树
        }

        int mid = fin;                                  // 将分割节点保存起来，而 fin 节点继续向右遍历
        while (postorder[fin] > postorder[right]){      // 找到第一个比 根节点小的 节点
            fin++;
        }

        return  fin == right                                    // 判断上述的根节点是否为 同个位置，判断 此树 是否正确。
                && recur(postorder, left, mid - 1)        // 左子树是否为 中序遍历，判断 此树的左子树 是否正确。
                && recur(postorder, mid, right - 1);      // 右子树是否为 中序遍历，right - 1 表示取出根节点，判断 此树的右子树 是否正确。
    }
}
